/*
Add and Search Word - Data structure design Total Accepted: 5838 Total Submissions: 28363 My Submissions Question Solution
Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

*/

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class TrieNode {
public:
	// Initialize your data structure here.

	bool isStr;
	unordered_map<char, TrieNode*> nexts;
	//vector<TrieNode*> nexts;
	TrieNode() :isStr(false) {

	}
};


class WordDictionary {
public:

	WordDictionary()
	{
		root = new TrieNode();
	}

	// Adds a word into the data structure.
	void addWord(string word) {
		TrieNode* cur = root;

		for (int i = 0; i < word.size(); i++)
		{
			char c = word[i];
			if (cur->nexts.find(c)==cur->nexts.end())
			{
				TrieNode *temp = new TrieNode();
				cur->nexts.insert(make_pair(c, temp));
			}
			cur = cur->nexts[c];
		}

		cur->isStr = true;
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		int n = word.size();
		return search(word, n, 0, root);

	}

	bool search(string word, int n, int pos, TrieNode* cur)
	{
		if (cur == NULL)
		{
			return false;
		}
		if (pos == n)
		{
			return cur->isStr;
		}

		if (word[pos] == '.')
		{
			unordered_map<char, TrieNode*>::iterator it = cur->nexts.begin();
			while (it != cur->nexts.end())
			{
				if (search(word, n, pos + 1, it->second))
					return true;
			}
		}
		else{
			char temp = word[pos];
			if (cur->nexts.find(temp)!= cur->nexts.end())
			{
				return search(word, n, pos + 1, cur->nexts[temp]);
			}
		
		}

		return false;

	}


private:
	TrieNode *root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

class TrieNode
{
public:
	bool isEnd;
	TrieNode *children[26];
	TrieNode() : isEnd(false)
	{
		for (int i = 0; i < 26; i++)
		{
			children[i] = NULL;
		}
	}
};

class WordDictionary {
public:
	WordDictionary()
	{
		root = new TrieNode();
	}

	// Adds a word into the data structure.
	void addWord(string word) {
		TrieNode *cur = root;
		for (int i = 0; i < word.length(); i++)
		{
			int index = word[i] - 'a';
			if (cur->children[index] == NULL)
			{
				cur->children[index] = new TrieNode();
			}

			cur = cur->children[index];
		}

		cur->isEnd = true;
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		int n = word.length();
		return search(word, n, 0, root);
	}

	bool search(string &word, int n, int pos, TrieNode *cur)
	{
		if (cur == NULL)
		{
			return false;
		}
		if (pos == n)
		{
			return cur->isEnd;
		}

		if (word[pos] == '.')
		{
			for (int i = 0; i < 26; i++)
			{
				if (cur->children[i])
				{
					if (search(word, n, pos + 1, cur->children[i]))
					{
						return true;
					}
				}
			}
		}
		else
		{
			int index = word[pos] - 'a';
			if (cur->children[index])
			{
				return search(word, n, pos + 1, cur->children[index]);
			}
		}

		return false;
	}
private:
	TrieNode *root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");




/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

int main(int argc, char* argv[])
{

	int num = 2;

	pair<int, int> temp;
	temp.first = 1;
	temp.second = 0;

	vector<pair<int, int>> prere;
	prere.push_back(temp);

	Solution s1;

	vector<int> result;

	result = s1.findOrder(num, prere);


	//ifs1.countPrimes(val);

	//strRes = s.findRepeatedDnaSequences(s1);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;s
/*
//string s1 = "GAGAGAGAGAGA";
string s1 = "GAGAGAGAGAGA";
vector<string> strRes;

TreeNode *root = new TreeNode(1);
TreeNode *left1 = new TreeNode(2);
TreeNode *left2 = new TreeNode(5);

TreeNode *right1 = new TreeNode(3);
TreeNode *right2 = new TreeNode(4);

root->left = left1;
left1->right = left2;

root->right = right1;
right1->right = right2;

//vector<char> level1({ '1', '1', '1', '1', '0' });
//vector<char> level2({ '1', '1', '0', '1', '0' });
//vector<char> level3({ '1', '1', '0', '0', '0' });
//vector<char> level4({ '0', '0', '0', '0', '0' });


vector<vector<char>> grid;
grid.push_back(level1);
grid.push_back(level2);
grid.push_back(level3);
grid.push_back(level4);ss
ListNode *head = new ListNode(1);
ListNode *head1 = new ListNode(2);
ListNode *head2 = new ListNode(6);
ListNode *head3 = new ListNode(3);
ListNode *head4 = new ListNode(4);
ListNode *head5 = new ListNode(5);

ListNode *head6 = new ListNode(6);

head->next = head1;
head1->next = head2;
head2->next = head3;
head3->next = head4;
head4->next = head5;
head5->next = head6;
int val = 6;
*/
